Batch 2 - Class 40 - Game Theory - Nim Games II

• Number of cards -  There are nine cards on a table labeled by numbers 1 through 9. Alice and Bob take turns choosing one card. The first player who acquires three cards that total 15 wins. Find the winning strategy
• Same as tic tac toe! and Magic square

• Review NIM
• Play one pile NIM again - say (1,2,3) NIM with a pile of 21 - Person to take the last piece wins
• What happens if person to take the last piece loses?

• Nim - Start with several piles of stones. A legal move consists of removing one or more stones from any one pile. The person who removes the last stone wins.
• What happens if there is only one pile?
• If the game has only two piles, what is the winning strategy?
• What if the game starts with three piles of 17, 11, and 8 stones?
• What is the general strategy for winning Nim games no matter how many piles there are? 
• In solution, if kids don't understand binary, do it as per comment on https://plus.maths.org/content/play-win-nim - Each power of two must have a partner

• 20 digit number - Two players take turn writing a 20 digit number left to right. If the number is divisible by 3, Bob wins. Else Alice. When does who win? (Answer: If Bob starts, Bob loses. If Alice starts, Bob Wins)

• Multiplying to 1000 -  Alice calls out any integer between 2 and 9, Bob multiplies it by any integer between 2 and 9, then Alice multiplies the new number by any integer between 2 and 9, and so on. The player who first gets a number bigger than 1000 wins.
• Empty and Divide -  (Ferguson (1998)) There are two boxes. Initially, one box contains m chips and the other contains n chips. Such a position is denoted by (m, n), where m > 0 and n > 0. The two players alternate moving. A move consists of emptying one of the boxes, and dividing the contents of the other between the two boxes with at least one chip in each box. There is a unique terminal position, namely (1, 1). Last player to move wins. Find all P-positions.
• Answer: The person who has an even pile available wins. The person who has two odd piles to work on loses.